{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 72. 编辑距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。\n",
    "\n",
    "你可以对一个单词进行如下三种操作：\n",
    "\n",
    "插入一个字符\n",
    "\n",
    "删除一个字符\n",
    "\n",
    "替换一个字符\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: word1 = \"horse\", word2 = \"ros\"\n",
    "输出: 3\n",
    "解释: \n",
    "horse -> rorse (将 'h' 替换为 'r')\n",
    "rorse -> rose (删除 'r')\n",
    "rose -> ros (删除 'e')\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: word1 = \"intention\", word2 = \"execution\"\n",
    "输出: 5\n",
    "\n",
    "解释: \n",
    "intention -> inention (删除 't')\n",
    "inention -> enention (将 'i' 替换为 'e')\n",
    "enention -> exention (将 'n' 替换为 'x')\n",
    "exention -> exection (将 'n' 替换为 'c')\n",
    "exection -> execution (插入 'u')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 动态规划，递归实现，dp(i,j)表示word1的前i个字母和word2的前j个字母匹配的最小代价\n",
    "def minDistance(word1, word2):\n",
    "    \n",
    "    def dp(i, j):\n",
    "        if i == 0:\n",
    "            return j\n",
    "        if j == 0:\n",
    "            return i\n",
    "        return 1 + min(dp(i-1,j), dp(i,j-1), dp(i-1,j-1) - (word1[i-1] == word2[j-1]))\n",
    "    \n",
    "    return dp(len(word1), len(word2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minDistance('horse', 'ros')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minDistance('intention', 'execution')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minDistance('abcdefg', 'abcdefg')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minDistance('abcdefg', 'gfedcba')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minDistance('baba', '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minDistance('', '')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 32. 最长有效括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: \"(()\"\n",
    "输出: 2\n",
    "\n",
    "解释: 最长有效括号子串为 \"()\"\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: \")()())\"\n",
    "输出: 4\n",
    "\n",
    "解释: 最长有效括号子串为 \"()()\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用栈\n",
    "def longest_valid_parentheses(s):\n",
    "    max_length = 0 # 最大合法子串长度\n",
    "    stack = [-1]\n",
    "    \n",
    "    for i, val in enumerate(s):\n",
    "        if val == '(':\n",
    "            stack.append(i) # 如果遇到（则将下标入栈\n",
    "        elif stack:\n",
    "            stack.pop() # 如果遇到）则出栈，舍弃该元素\n",
    "            if stack:\n",
    "                max_length = max(max_length, i - stack[-1]) # 与当前合法字串的前一个栈顶的下标相减，得到合法子串长度\n",
    "            else:\n",
    "                stack.append(i) # 如果当前栈为空，则把当前下标入栈，作为新栈顶\n",
    "    return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses('(()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses(')()())')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses(')(()())(())(()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses('(()(()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses(')))(((')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用动态规划\n",
    "def longest_valid_parentheses2(s):\n",
    "    max_dp = 0\n",
    "    dp = [0] * len(s) # dp[i]代表s中前i个字符的最大有效子串，且该有效字串以s[i]结尾\n",
    "    \n",
    "    for i, val in enumerate(s):\n",
    "        if s[i] == ')' and i >= 1:\n",
    "            if s[i - 1] == '(':\n",
    "                # 000000000000000()\n",
    "                dp[i] = (dp[i - 2] if i - 2 >= 0 else 0) + 2\n",
    "            else:\n",
    "                # 000000(00000000))\n",
    "                j = dp[i - 1]\n",
    "                if i - j - 1 >= 0 and s[i - j - 1] == '(':\n",
    "                    dp[i] = j + (dp[i - j - 2] if i - j - 2 >=0 else 0) + 2\n",
    "        max_dp = max(max_dp, dp[i])\n",
    "    \n",
    "    return max_dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses2('(()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses2(')()())')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses2(')(()())(())(()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses2('(()(()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses2(')))(((')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "longest_valid_parentheses2('')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 70. 爬楼梯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设你正在爬楼梯。需要 n 阶你才能到达楼顶。\n",
    "\n",
    "每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？\n",
    "\n",
    "注意：给定 n 是一个正整数。\n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入： 2\n",
    "输出： 2\n",
    "\n",
    "解释： 有两种方法可以爬到楼顶。\n",
    "1.  1 阶 + 1 阶\n",
    "2.  2 阶\n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入： 3\n",
    "输出： 3\n",
    "\n",
    "解释： 有三种方法可以爬到楼顶。\n",
    "1.  1 阶 + 1 阶 + 1 阶\n",
    "2.  1 阶 + 2 阶\n",
    "3.  2 阶 + 1 阶"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.special import comb\n",
    "\n",
    "# 直接用组合公式计算得出\n",
    "def climb_stairs(n):\n",
    "    return sum([comb(n - i, i) for i in range(n // 2 + 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.0"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8.0"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 动态规划，dp[i]代表前i个台阶存在的方法数量\n",
    "def climb_stairs2(n):\n",
    "    dp = [0] * (n + 1)\n",
    "    dp[0] = 1\n",
    "    dp[1] = 1\n",
    "    for i in range(2, n + 1):\n",
    "        # 最后一步存在两种选择：跨一步或跨两步，跨一步有dp[i-1]种方法，跨两步有dp[i-2]种方法\n",
    "        dp[i] = dp[i - 1] + dp[i - 2]\n",
    "    return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs2(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs2(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs2(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import sqrt, pow\n",
    "\n",
    "# 斐波那契数列公式\n",
    "def climb_stairs3(n):\n",
    "    sqrt5 = sqrt(5)\n",
    "    fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1)\n",
    "    return int(fibn / sqrt5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs3(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs3(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "climb_stairs3(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 300. 最长上升子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个无序的整数数组，找到其中最长上升子序列的长度。\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: [10,9,2,5,3,7,101,18]\n",
    "输出: 4 \n",
    "\n",
    "解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。\n",
    "\n",
    "说明:\n",
    "\n",
    "可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。\n",
    "你算法的时间复杂度应该为 O(n2) 。\n",
    "\n",
    "进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用动态规划，dp[i]代表恰好以第i个元素结尾的最长上升子串的长度，这就需要确认nums[i]应该接在哪个子串后面\n",
    "# 遍历前面所有的dp[i]，选符合上升要求的最长子串，接在其后面，dp值+1\n",
    "def length_of_LIS(nums):\n",
    "    if not nums: return 0\n",
    "    \n",
    "    length = len(nums)\n",
    "    dp = [1] * length\n",
    "    \n",
    "    for i in range(length):\n",
    "        for j in range(i):\n",
    "            if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1)\n",
    "    \n",
    "    return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS([10,9,2,5,3,7,101,18])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS([9,1,8,2,7,3,6,4,5,5,4,6,3,7,2,8,1,9])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS([3,2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS([1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 贪心算法+二分查找\n",
    "def length_of_LIS2(nums):\n",
    "    if not nums: return 0\n",
    "    \n",
    "    tail = [nums[0]]\n",
    "    for num in nums[1:]:\n",
    "        if num > tail[-1]:\n",
    "            tail.append(num)\n",
    "            continue\n",
    "        \n",
    "        # 二分查找\n",
    "        left = 0\n",
    "        right = len(tail) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if num > tail[mid]:\n",
    "                left = mid + 1 # 保证比num大\n",
    "            else:\n",
    "                right = mid\n",
    "        tail[left] = num\n",
    "            \n",
    "    return len(tail)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS2([10,9,2,5,3,7,101,18])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS2([9,1,8,2,7,3,6,4,5,5,4,6,3,7,2,8,1,9])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS2([3,2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS2([1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length_of_LIS2([])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 322. 零钱兑换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: coins = [1, 2, 5], amount = 11\n",
    "输出: 3 \n",
    "\n",
    "解释: 11 = 5 + 5 + 1\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: coins = [2], amount = 3\n",
    "输出: -1\n",
    "\n",
    "说明:\n",
    "你可以认为每种硬币的数量是无限的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 用栈实现多重循环遍历，优先搜索面值最大，数量最大的方案，如果能符合总金额则立即返回\n",
    "def coin_change(coins, amount):\n",
    "    if not coins: return -1\n",
    "    \n",
    "    size = len(coins)\n",
    "    sorted_coins = sorted(coins, reverse=True)\n",
    "    nums = []\n",
    "    left = amount\n",
    "    \n",
    "    while True:\n",
    "        if len(nums) == size:\n",
    "            nums.pop()\n",
    "            while nums:\n",
    "                nums[-1] -= 1\n",
    "                if nums[-1] < 0:\n",
    "                    nums.pop()\n",
    "                else:\n",
    "                    break\n",
    "            if not nums: return -1\n",
    "        nums.append(left // sorted_coins[len(nums)])\n",
    "        left = amount - sum(num * sorted_coins[i] for i, num in enumerate(nums))\n",
    "        if left == 0: return sum(nums), list(zip(sorted_coins, nums))\n",
    "    \n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, [(5, 2), (2, 0), (1, 1)])"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change([1, 2, 5], 11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6, [(11, 1), (7, 0), (3, 5)])"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change([3, 7, 11], 26)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, [(11, 2), (7, 0), (3, 2)])"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change([3, 7, 11], 28)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change([3, 5], 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, [(1, 1)])"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change([1], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change([], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用动态规划，dp[i]代表面值i所需的最少硬币数量\n",
    "def coin_change2(coins, amount):\n",
    "    if not coins: return -1\n",
    "    \n",
    "    size = len(coins)\n",
    "    buffer = [None] * (amount + 1) # 结果缓存\n",
    "    \n",
    "    def dp(i):\n",
    "        if i < 0: return float('inf')\n",
    "        if i == 0: return 0\n",
    "        if buffer[i]: return buffer[i]\n",
    "        min_dp = float('inf')\n",
    "        for coin in coins:\n",
    "            min_dp = min(min_dp, dp(i - coin)) # 遍历差一枚硬币的最佳情况\n",
    "        buffer[i] = 1 + min_dp\n",
    "        return buffer[i]\n",
    "    \n",
    "    res = dp(amount)\n",
    "    if res < float('inf'):\n",
    "        return res\n",
    "    else:\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change2([1, 2, 5], 11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change2([3, 7, 11], 26)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change2([3, 7, 11], 28)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change2([3, 5], 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change2([1], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change2([], 1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
